<h2>Problem 64</h2>
<div style="color:#666;font-size:80%;">27 February 2004</div><br />
<div class="problem_content">
<p>All square roots are periodic when written as continued fractions and can be written in the form:</p>
<div style="margin-left:20px;">
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' /><var>N</var> = <var>a</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /> +</td>
<td colspan="3" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> +</td>
<td colspan="2" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" /> +</td>
<td style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>3</sub><img src="" style="display:none;" alt=")" /> + ...</td>
</tr>
</table>
</div>
<p>For example, let us consider <img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23:</p>
<div style="margin-left:20px;">
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23 = 4 + <img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23 &mdash; 4 = 4 +&nbsp;</td>
<td style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
<td>&nbsp;= 4 +&nbsp;</td>
<td colspan="2" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td><div style="text-align:center;">1<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span></div></td>
<td>&nbsp;</td>
<td>1 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23 &ndash; 3</span><br />7</div></td>
</tr>
</table>
</div>
<p>If we continue we would get the following expansion:</p>
<div style="margin-left:20px;">
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23 = 4 +</td>
<td colspan="4" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>1 +</td>
<td colspan="3" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>3 +</td>
<td colspan="2" style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>1 +</td>
<td style="border-bottom:1px solid #000;"><div style="text-align:center;">1</div></td>
</tr>
<tr>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>&nbsp;</td>
<td>8 + ...</td>
</tr>
</table>
</div>
<p>The process can be summarised as follows:</p>
<div style="margin-left:20px;">
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>0</sub><img src="" style="display:none;" alt=")" /> = 4,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">1<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+4</span><br />7</div></td>
<td>&nbsp;=&nbsp;1 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span><br />7</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" /> = 1,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">7<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">7(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+3)</span><br />14</div></td>
<td>&nbsp;=&nbsp;3 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span><br />2</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>2</sub><img src="" style="display:none;" alt=")" /> = 3,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">2<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">2(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+3)</span><br />14</div></td>
<td>&nbsp;=&nbsp;1 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span><br />7</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>3</sub><img src="" style="display:none;" alt=")" /> = 1,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">7<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">7(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+4)</span><br />7</div></td>
<td>&nbsp;=&nbsp;8 +&nbsp;</td>
<td><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>4</sub><img src="" style="display:none;" alt=")" /> = 8,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">1<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+4</span><br />7</div></td>
<td>&nbsp;=&nbsp;1 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span><br />7</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>5</sub><img src="" style="display:none;" alt=")" /> = 1,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">7<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">7(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+3)</span><br />14</div></td>
<td>&nbsp;=&nbsp;3 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span><br />2</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>6</sub><img src="" style="display:none;" alt=")" /> = 3,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">2<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;3</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">2(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+3)</span><br />14</div></td>
<td>&nbsp;=&nbsp;1 +&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span><br />7</div></td>
</tr>
<tr>
<td><var>a</var><img src="" style="display:none;" alt="_(" /><sub>7</sub><img src="" style="display:none;" alt=")" /> = 1,</td>
<td>&nbsp;</td>
<td><div style="text-align:center;">7<br /><span style="border-top:1px solid #000;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</span></div></td>
<td>&nbsp;=&nbsp;</td>
<td><div style="text-align:center;"><span style="border-bottom:1px solid #000;">7(<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23+4)</span><br />7</div></td>
<td>&nbsp;=&nbsp;8 +&nbsp;</td>
<td><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23&mdash;4</td>
</tr>
</table>
</div>
<p>It can be seen that the sequence is repeating. For conciseness, we use the notation <img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.</p>

<p>The first ten continued fraction representations of (irrational) square roots are:</p>
<p style="margin-left:20px;"><img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />2=[1;(2)], period=1<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />3=[1;(1,2)], period=2<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />5=[2;(4)], period=1<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />6=[2;(2,4)], period=2<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />7=[2;(1,1,1,4)], period=4<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />8=[2;(1,4)], period=2<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />10=[3;(6)], period=1<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />11=[3;(3,6)], period=2<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />12= [3;(2,6)], period=2<br />
<img src='images/symbol_radic.gif' width='14' height='16' alt='&radic;' border='0' style='vertical-align:middle;' />13=[3;(1,1,1,1,6)], period=5</p>
<p>Exactly four continued fractions, for <var>N</var> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 13, have an odd period.</p>
<p>How many continued fractions for <var>N</var> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 10000 have an odd period?</p>
</div><br />
